一、Geom-GCN [2020]

《Geom-GCN: Geometric graph convolutional networks》

1. 消息传递神经网络（Message-Passing Neural Networks:MPNN ）（如 GNN, ChebNet, GG-NN, GCN）已经成功地应用于各种实际应用中的图表示学习（graph representation learning）。在 MPNN 的每一层网络中，每个节点向邻域内的其它节点发送该节点的 representation 作为消息（message），然后通过聚合从邻域内收到的所有消息来更新它的 representation。其中，邻域通常定义为图中相邻节点的集合。通过采用排列不变（permutation-invariant）的聚合函数（如 sum, max, mean 聚合函数），MPNN 能够学到同构图（isomorphic graph）（即，拓扑结构相同的图）的不变的representation 。

   虽然现有的 MPNN 已经成功应用于各种场景，但是 MPNN 聚合器（aggregator）的两个基本缺陷限制了它们表示图结构数据的能力：

   • 首先，聚合器丢失了邻域的结构信息。

     排列不变性（permutation invariance）是任何图学习方法的基本要求。为满足这一要求现有的 MPNN 采用了排列不变的聚合函数，这些聚合函数将来自邻域的所有消息视为一个集合。例如，GCN 只是对所有一阶邻居的归一化消息求和。这种聚合会丢失邻域节点的结构信息，因为它无法区分不同节点的消息。因此，在聚合之后，我们也就无法知晓哪个节点对最终的聚合输出做出了贡献。

     如果不对邻域结构进行建模，现有的 MPNN 将无法区分某些非同构图（non-isomorphic graph）。在这些非同构图中，MPNN 可能将不同的邻域结构映射为相同的feature representation，这显然不适合graph representation learning。与 MPNN 不同，经典的 CNN 通过特殊的聚合器（即，滤波器）来避免这个问题从而能够区分每个 input unit ，其中这些聚合器具有结构化的感受野 （receiving filed）并定义在网格（grid）上。

     正如论文 《Geom-GCN: Geometric graph convolutional networks》的实验所示，这些邻域结构信息通常包含图中拓扑模式（topology pattern）的线索，因此应该提取并被应用于学习图的更有区分度的 rerepenstation。

   • 其次，聚合器缺乏捕获异配图（disassortative graph）（指的是相似的节点没有聚合在一起的图）中长程依赖（long-range dependency）的能力。

     在 MPNN 中，邻域被定义为 $k$$k$ 阶邻居的集合，$k\ge 1$$k\ge 1$ 。换句话讲，聚合器只会聚合来自附近节点的消息。这种聚合方式的 MPNN 倾向于对图中相近的节点学到相似的representation。这意味这些MPNN 可能是同配图（assortative graph）（如引文网络、社区网络）representation learning的理想方法。在这些同配图中，节点的同质性（homophily）成立，即相似的节点更可能在图中相近，图中相近的节点更可能相似。

     而对于节点同质性不成立的异配图，此时有些高度相似的节点在图中距离较远。这种情况下MPNN 的表示能力可能会受到严重限制，因为它们无法从距离遥远、但是包含丰富信息的相似节点中捕获重要特征。

     解决这个限制的简单策略是使用多层架构，以便从远程节点接收消息。例如，虽然经典 CNN 中的卷积滤波器只能捕获局部数据，其单层卷积层的表示能力受限，但是通过堆叠多层卷积层，CNN 可以学到复杂的全局表示。

     和 CNN 不同，多层 MPNN 很难学到异配图的良好representation，这里有两个原因：

     • 一方面，在多层 MPNN 中，来自远程节点的相关信息和来自近端节点的大量无关信息无差别地混合在一起，意味着相关信息被冲洗掉（washed out），无法有效地提取。

     • 另一方面，在多层 MPNN 中，不同节点的representation将变得非常相似，因为每个节点的representation实际上承载了关于整个图的信息，即 over-smooth 。

   在论文《Geom-GCN: Geometric graph convolutional networks》 中，作者从两个基本观察出发，克服了图神经网络的上述缺陷：

   • 由于连续空间（continuous space）的平稳性（stationarity）、局部性（locality）、组合性（compositionality），经典的神经网络有效地解决了类似的局限。

   • 网络几何（network geometry）有效地弥补了连续空间和和图空间之间的 gap 。

     网络几何的目的是通过揭示潜在的连续空间来理解网络，它假设节点是从潜在的连续空间中离散地采样，并根据节点之间的距离来构建边。在潜在空间中，图中复杂的拓扑模式（如子图、社区、层次结构）可以保留下来，并以直观的几何方式呈现。

   受这两个观察结果的启发，作者对图神经网络中的聚合方案提出了一个启发性问题：图上的聚合方案能否受益于连续的潜在空间？例如使用连续的潜在空间中的几何结构来构建邻域，从而捕获图中的长程依赖？

   为回答上述问题，作者提出了一种新的图神经网络聚合scheme，称作几何聚合方案（geometric aggregation scheme）。在该方案中，作者通过node embedding 将一个图映射到一个连续的潜在空间，然后利用潜在空间中定义的几何关系来构建邻域从而进行聚合。同时，作者还设计了一个基于结构邻域的 bi-level 聚合器来更新节点的 representation，保证了图结构数据的排列不变性。和现有的 MPNN 相比，该方法提取了更多的图结构信息，并通过连续空间中定义的邻域来聚合远程节点的feature representation。

   然后，作者提出了几何聚合方案在图卷积网络上的实现，称作 Geom-GCN ，从而在图上执行 transductive learning、node classification 。作者设计了特定的几何关系来分别从欧式空间和 hyperbolic embedding 空间中构建结构邻域 （structural neighborhood）。作者选择不同的 embedding 方法将图映射到适合不同 application 的潜在空间，在该潜在空间中保留了适当的图拓扑模式。

   最后，作者在大量公开的图数据集上对 Geom-GCN 进行了实验，证明了 Geom-GCN 达到了 SOTA 效果。

   总之，论文的主要贡献如下：

   • 作者提出了一种新的几何聚合方案用于图神经网络，它同时在图空间和潜在空间中运行，从而克服上述两个局限性。

   • 作者提出了该方案的一个实现，即 Geom-GCN，用于图中的 transductive learning。

   • 作者通过在几个具有挑战性的 benchmark 上与 SOTA 方法进行广泛的比较来验证和分析 Geom-GCN 。

2. 相关工作：参考原始论文。

1.1 几何聚合方案

1. 这里首先介绍几何聚合方案，然后概述它和现有工作相比的优点和缺点。

1.1.1 基础模块

1. 如下图所示，几何聚合方案由三个模块组成：node embedding （A1 和 A2）、结构邻域（B1 和 B2）、bi-level 聚合（C）。图中：

   • A1-A2：原始图（A1）被映射到一个潜在的连续空间（A2）。

   • B1-B2：结构邻域（B2）。为可视化，我们放大了中心节点（红色）周围的邻域。关系算子 $\tau$$\tau$ 由彩色的 3x3 网格表示，每个单元格代表了和红色目标节点的几何关系（即几何位置是左上、左下、右上、右下等等）。

   • C：在结构邻域上的 bi-level 聚合。虚线和实线箭头分别表示 low-level 聚合和 high-level 聚合。蓝色箭头和绿色箭头分别表示图上的聚合以及潜在空间上的聚合。

   

2. node embedding：这是一个基础组件，它将图中的节点映射到潜在的连续空间（latent continuous space）。

   令图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G=(\mathcal V, \mathcal E)$ ，其中 $\mathcal{V}=\{v_1,v_2,\cdots ,v_n\}$$\mathcal V = \{v_1,v_2,\cdots,v_n\}$ 为节点集合， $\mathcal{E}$$\mathcal E$ 为边集合。每个节点 $v\in \mathcal{V}$$v\in \mathcal V$ 关联一个特征向量 ${\overrightarrow{\mathbf{x}}}_v\in {\mathbb{R}}^{d_f}$$\mathbf{\vec x}_v\in \mathbb R^{d_f}$ ，其中 $d_f$$d_f$ 为特征向量维度。

   令 $f:v\to {\overrightarrow{\mathbf{z}}}_v\in {\mathbb{R}}^d$$f:v\rightarrow \mathbf{\vec z}_v \in \mathbb R^d$ 为一个映射函数，它将节点 $v$$v$ 映射到representation 向量 ${\overrightarrow{\mathbf{z}}}_v$$\mathbf{\vec z}_v$ ，其中 $d$$d$ 为 representation 向量的维度。这可以理解为将节点 $v$$v$ 映射到潜在的连续的 $d$$d$ 维空间， ${\overrightarrow{\mathbf{z}}}_v$$\mathbf{\vec z}_v$ 为节点 $v$$v$ 在这个连续空间中的位置。在映射过程中，图的结构和属性将被保留，并显示为潜在空间中的几何结构（geometry）。这里可以使用各种 embedding 方法来得到不同的潜在连续空间（《A comprehensive survey of graph embedding: Problems, techniques, and applications》、《A united approach to learning sparse attributed network embedding》）。

3. 结构邻域（structural neighborhood）：基于离散的图空间和连续的潜在空间，我们构建一个结构邻域 ${\mathcal{N}}_v=(\{{\mathcal{N}}_g(v),{\mathcal{N}}_s(v)\},\tau )$$\mathcal N_v = (\{\mathcal N_g(v), \mathcal N_s(v)\},\tau)$ ，它由一组邻域 $\{{\mathcal{N}}_g(v),{\mathcal{N}}_s(v)\}$$\{\mathcal N_g(v),\mathcal N_s(v)\}$ 以及一个邻域上的关系算子 $\tau$$\tau$ 组成。

   • ${\mathcal{N}}_g(v)$$\mathcal N_g(v)$ 为节点 $v$$v$ 在图上的相邻节点集合 ${\mathcal{N}}_g(v)=\{u\mid u\in \mathcal{V},(u,v)\in \mathcal{E}\}$$\mathcal N_g(v)=\{u\mid u\in \mathcal V, (u,v)\in \mathcal E\}$ 。

   • ${\mathcal{N}}_s(v)$$\mathcal N_s(v)$ 为节点 $v$$v$ 在潜在空间中相邻节点集合 ${\mathcal{N}}_s(v)=\{u\mid u\in \mathcal{V},\text{dist}({\overrightarrow{\mathbf{z}}}_u,{\overrightarrow{\mathbf{z}}}_v)<\rho \}$$\mathcal N_s(v) = \{u\mid u\in \mathcal V,\text{dist}(\mathbf{\vec z}_u,\mathbf{\vec z}_v)\lt \rho\}$ ，其中 $\text{dist}(\cdot ,\cdot )$$\text{dist}(\cdot,\cdot)$ 为潜在空间中的距离函数， $\rho$$\rho$ 为提前给定的距离参数。因此 ${\mathcal{N}}_s(v)$$\mathcal N_s(v)$ 给出了在潜在空间中和节点 $v$$v$ 距离小于 $\rho$$\rho$ 的节点集合。

     和 ${\mathcal{N}}_g(v)$$\mathcal N_g(v)$ 相比，${\mathcal{N}}_s(v)$$\mathcal N_s(v)$ 可能包含那些和节点 $v$$v$ 相似、但是在图上远离节点 $v$$v$ 的其它节点。因为映射函数 $f$$f$ 可以保持这种相似性，因此这些节点在潜在空间中都被映射到节点 $v$$v$ 的附近。通过聚合 ${\mathcal{N}}_s(v)$$\mathcal N_s(v)$ 上的邻域节点，我们可以捕获到异配图上的长程依赖。

   • 关系算子 $\tau$$\tau$ 是定义在潜在空间上的函数。给定节点 $v$$v$ 和 $u$$u$ 的一个有序的representation pair 对 $({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u)$$(\mathbf{\vec z}_v,\mathbf{\vec z}_u)$ 作为 $\tau$$\tau$ 的输入，其输出为一个离散的变量 $r$$r$ ，该变量指示潜在空间中从 $v$$v$ 到 $u$$u$ 的几何关系（geometric relationship）：

     $$\tau :({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u)\to r\in \mathcal{R}$$

     其中 $\mathcal{R}$$\mathcal R$ 为几何关系的集合。例如在上图的 B2 中， $\mathcal{R}$$\mathcal R$ 包含九种关系：{左上、中上、右上、左中、相同、右中、左下、中下、右下 } 。

     根据不同的潜在空间和不同的应用，$\mathcal{R}$$\mathcal R$ 可以选择任意的关系集合。唯一的要求是：给定一对有序的 representation pair 对，它们的关系应该是唯一的。

4. bi-level 聚合：借助结构邻域 ${\mathcal{N}}_v$$\mathcal N_v$ ，我们为图神经网络提出了一种新颖的 bi-level 聚合方案来更新节点的 hidden feature。bi-level 聚合方案由两个聚合函数组成，它可以有效地提取邻域节点的结构信息，并保持图的排列不变性。

   令 ${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 为节点 $v$$v$ 在第 $l$$l$ 层的 hidden feature，其中 ${\overrightarrow{\mathbf{h}}}_v^{(0)}={\overrightarrow{\mathbf{x}}}_v$$\mathbf{\vec h}_v^{(0)} = \mathbf{\vec x}_v$ 为节点特征。则节点 $v$$v$ 在第 $l+1$$l+1$ 层的 hidden feature ${\overrightarrow{\mathbf{h}}}_v^{(l+1)}$$\mathbf{\vec h}_v^{(l+1)}$ 为的更新为：

   注意：节点 $v$$v$ 有两种 representation：${\overrightarrow{\mathbf{z}}}_v$$\mathbf{\vec z}_v$ 为 node embedding 用于构建结构邻域（通常具有较小的维度）、${\overrightarrow{\mathbf{h}}}_v^{(l)}$$\mathbf{\vec h}_v^{(l)}$ 为 node representation 用于具体的任务（图，节点分类）。

   • low-level 聚合：

     $${\overrightarrow{\mathbf{e}}}_{(i,r)}^{(v,l+1)}=p\left(\{{\overrightarrow{\mathbf{h}}}_u^{(l)}\mid u\in {\mathcal{N}}_i(v),\tau ({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u)=r\}\right),\mathrm{\forall }i\in \{g,s\},\mathrm{\forall }r\in \mathcal{R}$$

     在 low-level 聚合，处于相同类型的邻域 $i$$i$ 且具有相同集合关系 $r$$r$ 的节点的 hidden feature 通过聚合函数 $p$$p$ 聚合到虚拟节点。

     • 这个虚拟节点的特征是 ${\overrightarrow{\mathbf{e}}}_{(i,r)}^{(v,l+1)}$$\mathbf{\vec e}_{(i,r)}^{(v,l+1)}$ ，并且这个虚拟节点由 $(i,r)$$(i,r)$ 索引，该索引对应于邻域 $i$$i$ 和关系 $r$$r$ 的组合。

     • $p$$p$ 要求使用排列不变函数，如 $L_p$$L_p$ 范数，$p=1,2,\mathrm{\infty }$$p=1,2,\infty$ 分别对应于 average pooling, enerage pooling, max pooling 。

     low-level 聚合如上图 C1 的虚线箭头所示。

   • high-level 聚合：

     $${\overrightarrow{\mathbf{m}}}_v^{(l+1)}=q\left(\{({\overrightarrow{\mathbf{e}}}_{(i,r)}^{(v,l+1)},(i,r))\mid i\in \{g,s\},r\in \mathcal{R}\}\right)$$

     在 high-level，虚拟节点由函数 $q$$q$ 进一步聚合。函数 $q$$q$ 的输入既包含了虚拟节点的特征 ${\overrightarrow{\mathbf{e}}}_{i,r}^{v,l+1}$$\mathbf{\vec e}_{i,r}^{v,l+1}$ ，也包含了虚拟节点的索引 $(i,r)$$(i,r)$ （用于识别虚拟节点的身份）。即 $q$$q$ 可以将有序对象作为输入（如拼接），从而区分不同虚拟节点，从而显式提取邻域中的结构信息。

     这里聚合了图空间邻域和潜在空间邻域，共两种类型的邻域。也可以构建 $N$$N$ 个潜在空间邻域，从而得到 $N+1$$N+1$ 中类型的邻域。

   • 非线性映射：

     $${\overrightarrow{\mathbf{h}}}_v^{(l+1)}=\sigma \left({\mathbf{W}}_l{\overrightarrow{\mathbf{m}}}_v^{(l+1)}\right)$$

     high-level 聚合的输出是向量 ${\overrightarrow{\mathbf{m}}}_v^{l+1}$$\mathbf{\vec m}_v^{l+1}$ ，然后通过非线性变换可以得到节点 $v$$v$ 的新的 hidden feature ${\overrightarrow{\mathbf{h}}}_v^{l+1}$$\mathbf{\vec h}_v^{l+1}$ 。其中：

     • ${\mathbf{W}}_l$$\mathbf W_l$ 为待学习的、所有节点共享的、在网络第 $l$$l$ 层的权重矩阵。

     • $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数，如 ReLU 。

1.1.2 排列不变性

1. 排列不变性（permutation invariance）是图神经网络中聚合器的基本要求，随后我们将证明我们提出的 bi-level 聚合公式能够保证邻域节点的任何排列都不变。

2. 图的排列不变映射的定义：给定一个双射函数 $\psi :\mathcal{V}\to \mathcal{V}$$\psi: \mathcal V\rightarrow \mathcal V$ 为节点的一个排列，它将节点 $v\in \mathcal{V}$$v\in\mathcal V$ 映射为 $\psi (v)\in \mathcal{V}$$\psi(v)\in \mathcal V$ 。 令 ${\mathcal{V}}^{\prime },{\mathcal{E}}^{\prime }$$\mathcal V^\prime, \mathcal E^\prime$ 为经过 $\psi$$\psi$ 映射后的节点集合和边集合。对于图的映射 $\varphi (\mathcal{G})$$\phi(\mathcal G)$ ，如果对任意给定的 $\psi$$\psi$ 都有 $\varphi (\mathcal{G})=\varphi ({\mathcal{G}}^{\prime })$$\phi(\mathcal G) = \phi(\mathcal G^\prime)$ ，其中 ${\mathcal{G}}^{\prime }=({\mathcal{V}}^{\prime },{\mathcal{E}}^{\prime })$$\mathcal G^\prime = (\mathcal V^\prime, \mathcal E^\prime)$ ，则我们称图的映射 $\varphi (\mathcal{G})$$\phi(\mathcal G)$ 是排列不变的。

3. 引理：对于组合函数 ${\varphi }_1\circ {\varphi }_2(\mathcal{G})$$\phi_1\circ\phi_2(\mathcal G)$ ，如果 ${\varphi }_2(\mathcal{G})$$\phi_2(\mathcal G)$ 是排列不变的，则整个组合函数 ${\varphi }_1\circ {\varphi }_2$$\phi_1\circ\phi_2$ 为排列不变的。

   证明：令 ${\mathcal{G}}^{\prime }$$\mathcal G^\prime$ 为图 $\mathcal{G}$$\mathcal G$ 经过排列函数 $\psi$$\psi$ 之后的同构图（isomorphic graph），如果 ${\varphi }_2(\mathcal{G})$$\phi_2(\mathcal G)$ 是排列不变的，则有 ${\varphi }_2(\mathcal{G})={\varphi }_2({\mathcal{G}}^{\prime })$$\phi_2(\mathcal G) = \phi_2(\mathcal G^\prime)$ 。因此，整个组合函数 ${\varphi }_1\circ {\varphi }_2(\mathcal{G})$$\phi_1\circ\phi_2(\mathcal G)$ 是排列不变的，因为有 ${\varphi }_1\circ {\varphi }_2(\mathcal{G})={\varphi }_1\circ {\varphi }_2({\mathcal{G}}^{\prime })$$\phi_1\circ\phi_2(\mathcal G) = \phi_1\circ\phi_2(\mathcal G^\prime)$ 。

   ${\varphi }_1\circ {\varphi }_2(\mathcal{G})$$\phi_1\circ\phi_2(\mathcal G)$ 的含义是：${\varphi }_1({\varphi }_2(\mathcal{G}))$$\phi_1(\phi_2(\mathcal G))$ 。

4. 定理：给定图 $\mathcal{G}=(\mathcal{V},\mathcal{E})$$\mathcal G = (\mathcal V, \mathcal E)$ 及其结构邻域 ${\mathcal{N}}_v$$\mathcal N_v$ ，则 bi-level 聚合是排列不变的映射。

   证明：bi-level 聚合是一个组合函数，其中 low-level 聚合是 high-level 聚合的输入。因此，如果能够证明 low-level 聚合是排列不变的，则 bi-level 聚合是排列不变的。

   现在我们来证明 low-level 聚合是排列不变的。low-level 聚合由 $2\times |\mathcal{R}|$$2\times |\mathcal R|$ 个子聚合组成，每个子聚合对应于节点 $v$$v$ 的一个邻域类型 $i$$i$ 和关系类型 $r$$r$ 。

   • 首先，每个子聚合的输入都是排列不变的，因为 $i\in \{g,s\}$$i\in \{g,s\}$ 和 $r\in \mathcal{R}$$r\in \mathcal R$ 都是由给定的结构邻域 ${\mathcal{N}}_v$$\mathcal N_v$ 决定的，而这个结构邻域对于任何排列而言都是恒定的。

   • 其次，子聚合采用了排列不变的聚合函数 $p$$p$ ，因此 low-level 聚合是排列不变的。

1.1.3 与相关工作的比较

1. 这里讨论我们提出的几何聚合方案如何克服之前提到的两个缺点，即：如何有效地对邻域结构进行建模、如何捕获长程依赖。

   • 为了克服 MPNN 的第一个缺点，即丢失邻域中节点的结构信息，几何聚合方案利用潜在空间中节点之间的几何关系，然后使用 bi-level 聚合有效地提取信息，从而对结构信息进行显式建模。

     相反，现有的一些方法试图学习一些隐式的、类似于结构的信息，从而在聚合时区分不同的邻居。如 GAT（《Graph attention networks》）、 LGCL （《Large-scale learnable graph convolutional networks》）、 GG-NN （《Gated graph sequence neural networks》）等通过使用注意力机制以及节点/边的属性来学习来自不同邻居消息的权重。CCN 利用协方差架构来学习 structure-aware representation （《Covariant compositional networks for learning graphs》）。这些工作和我们之间的主要区别在于：我们利用潜在空间的几何信息提供了一种显式的、可解释的方式来建模节点邻域的结构信息。

     另外，我们的方法和现有的这些方法是正交的，因此可以容易地和现有方法融合从而进一步改善性能。具体而言，我们从图拓扑的角度利用几何关系，而其它方法更关注feature representation，这两个方面是互补的。

   • 为了克服 MPNN 的第二个缺点，即缺乏捕获远程依赖的能力，几何聚合方案以两种不同的方式对异配图中的远程关系进行建模：

     • 首先，可以将图中相似但是相距很远的节点映射到目标节点在潜在空间的邻域中，然后聚合这些邻域节点的representation。这种方式取决于保留节点相似性的适当的 embedding 方法。

     • 其次，结构信息使得该方法能够区分图中邻域中的不同节点。informative node和目标节点可能具有某些特殊的几何关系（如特定的角度、特定的距离）。因此相比uninformative node，informative node的相关的特征将以更高的权重传递给目标节点。

     最终通过整个消息传递过程间接捕获了长程依赖关系。

     此外， 《Representation learning on graphs with jumping knowledge networks》 中提出了一种方法 JK-Nets 通过在特征聚合期间 skip connection 来捕获长程依赖关系。

2. 有些文献构造了一些非同构（ non-isomorphic） 图（《Covariantcompositional networks for learning graphs》、《How powerful are graph neural networks? 》），它们无法被现有的 MPNN 聚合器（如均值、最大值）很好地区分。这里我们给出两个示例，它们来自于 《How powerful are graph neural networks?》。

   • 如下左图所示，每个节点都具有相同的特征 $a$$a$ ，经过映射 $f(\cdot )$$f(\cdot)$ 之后每个节点仍然保持相同。映射之后再经过常规的聚合器（如均值、最大值、最小值），仍然是 $f(a)$$f(a)$ 。因此左图的两个 graph 中，节点 $V_1$$V_1$ 的final representation都是相同的。即，均值聚合器和最大值聚合器无法区分这两个不同的图。

   • 相反，如果在聚合过程中应用结构邻域，则这两个图可以很容易地区分。应用结构邻域之后，其它节点和 $V_1$$V_1$ 之间具有不同的几何关系，如右图所示。以 $V_1$$V_1$ 的聚合为例：

     • 对于 $V_1$$V_1$ 的邻居节点，我们可以对不同的几何关系 $r$$r$ 采用不同的映射函数 $f_r,r\in \mathcal{R}$$f_r,r\in \mathcal R$ 。

     • 然后，两个图中的聚合器具有不同的输入，左边的输入为 $\{f_2(a),f_8(a)\}$$\{f_2(a), f_8(a)\}$ 、右边的输入为 $\{f_2(a),f_7(a),f_9(a)\}$$\{f_2(a),f_7(a),f_9(a)\}$ 。

     • 最终在两个图中，聚合器（平均值或最大值）对节点 $V_1$$V_1$ 输出不同的表示形式，从而区分两个图之间的拓扑差异。

1.2 Geom-GCN

1. 这里我们介绍 Geom-GCN，它是几何聚合方案在 GCN 上的具体实现，主要用于图的 transductive learning 。

   为实现几何聚合方案，需要给出其中的三个模块：node embedding、结构邻域、bi-level 聚合。

2. node embedding：如我们实验所示，仅保留图中的边以及距离模式的常见 embedding 方法已经可以使几何聚合方案受益。

   对于特定的应用，可以指定特定的 embedding 方法来建立合适的、保留特定拓扑结构（如层次结构）的潜在空间。我们使用了三种 embedding 方法，即：Isomap、Poincare Embedding、Struc2vec ，这导致了三种 Geom-GCN 变体：Geom-GCN-I、Geom-GCN-P、Geom-GCN-S。

   • Isomap 是一种广泛应用的 isometry embedding 方法，在该方法中，距离模式（最短路径的长度）被显式地保留在潜在空间中。

   • Poincare Embedding 和 Struc2vec 能够创建特定的潜在空间，分别保留图中的层次结构和局部结构。

   为了便于说明，我们的 embedding 空间维度为 2 （即 ${\overrightarrow{\mathbf{z}}}_v\in {\mathbb{R}}^2$$\mathbf{\vec z}_v\in \mathbb R^2$） 。

3. 结构邻域：节点 $v$$v$ 的结构邻域 ${\mathcal{N}}_v=(\{{\mathcal{N}}_g(v),{\mathcal{N}}_s(v)\},\tau )$$\mathcal N_v = (\{\mathcal N_g(v), \mathcal N_s(v)\},\tau)$ 同时包含图空间的邻域和潜在空间中的邻域。

   图空间邻域 ${\mathcal{N}}_g(v)$$\mathcal N_g(v)$ 由图中 $v$$v$ 的相邻节点组成，潜在空间中的邻域 ${\mathcal{N}}_s(v)$$\mathcal N_s(v)$ 由潜在空间中与 $v$$v$ 距离小于 $\rho$$\rho$ 的节点组成。这里我们将 $\rho$$\rho$ 从零逐渐增加，直到对于所有节点 $v$$v$ ， ${\mathcal{N}}_s(v)$$\mathcal N_s(v)$ 的平均邻域大小等于 ${\mathcal{N}}_g(v)$$\mathcal N_g(v)$ 的平均邻域大小。最终两个邻域平均大小相等的 $\rho$$\rho$ 就是我们需要的。

   另外对于不同的潜在空间我们使用不同的距离：在欧式空间中我们使用欧式距离；在双曲空间（hyperbolic space）中，我们通过两个节点在局部切平面上的欧式距离来近似测地线距离。

   我们简单地将几何算子 $\tau$$\tau$ 实现为二维欧式空间或双曲空间中两个节点之间相对位置的四种关系。即，关系集合 $\mathcal{R}=\{\text{upper left},\text{upper right},\text{lower left},\text{lower right }\}$$\mathcal R = \{\text{upper left},\text{upper right},\text{lower left},\text{lower right }\}$ ，并且 $\tau ({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u)$$\tau(\mathbf{\vec z}_v, \mathbf{\vec z}_u)$ 如下表所示。注意：我们在欧式空间中使用直角坐标系，在双曲空间中使用角坐标系。

   因为 embedding size = 2，所以划分为四种关系。

   也可以设计更复杂的几何算子 $\tau$$\tau$ ，如利用流形几何中的描述符结构，从而在邻域中保留更多、更丰富的结构信息。

   

4. bi-level 聚合：我们采用和 GCN 相同的归一化 hidden feature 聚合作为 low-level 聚合函数 $p$$p$ ：

   $${\overrightarrow{\mathbf{e}}}_{(i,r)}^{(v,l+1)}=\sum _{u\in {\mathcal{N}}_i(v),\tau ({\overrightarrow{\mathbf{z}}}_v,{\overrightarrow{\mathbf{z}}}_u)=r}\left(\sqrt{\text{deg}(v)\times \text{deg}(u)}\right)\times {\overrightarrow{\mathbf{h}}}_u^{(l)},\mathrm{\forall }i\in \{g,s\}$$

   其中 $\text{deg}(v)$$\text{deg}(v)$ 为节点 $v$$v$ 的 degree。聚合时仅考虑和节点 $v$$v$ 的关系为 $r$$r$ 的那些节点。

   对于最后一层我们使用均值聚合作为 high-level 聚合函数 $q$$q$ ， 除最后一层之外我们使用向量拼接作为聚合函数 $q$$q$ ：

   $${\overrightarrow{\mathbf{h}}}_v^{l+1}=\sigma \left({\mathbf{W}}_l(|{|}_{i\in \{g,s\},r\in \mathcal{R}}{\overrightarrow{\mathbf{e}}}_{(i,r)}^{(v,l+1)})\right)$$

   其中： ${\mathbf{W}}_l$$\mathbf W_l$ 为待学习的权重矩阵； $\sigma (\cdot )$$\sigma(\cdot)$ 为非线性激活函数，这里我们使用 ReLU 。

1.3 实验

1. 这里我们比较了 Geom-GCN 和 GCN, GAT 的性能，从而验证 Geom-GCN 的效果。

2. 数据集：我们使用 9 个图数据集：

   • 引文网络：Cora, Citeseer, Pubmed 是标准的引文网络 benchmark 数据集。

     在这些网络中，节点表示论文，边表示论文被另一篇论文引用，节点特征是论文的 bag-of-word 表示，节点标签是论文的学术主题。

   • WebkB 数据集：WebKB 由卡内基梅隆大学从各大学的计算机科学系收集的网页数据集，我们使用它的三个子集：Cornell, Texas, Wisconsin 。

     在这些网络中，节点代表网页，边代表网页之间的超链接，节点的特征是网页的 bag-of-word 表示。网页被人工分为五个类别：student, project, course, staff, faculty 。

   • Actor co-occurrence 数据集：该数据集是 film-directoractor-writer 网络导出的仅包含演员的子图。

     在该网络中，节点代表演员，边表示同一个维基百科上两个演员的共现，节点特征为该演员的维基百科页面上的关键词。根据演员的维基百科的词汇，我们将节点分为五类。

   这些数据集的统计信息如下表所示：

   

3. 实验配置：我们使用三种embedding 方法，即 Isomap、Poincare embedding、struc2vec ，从而构建三种 Geom-GCN 变体，即 Geom-GCN-I、Geom-GCN-P、Geom-GCN-S。

   • 所有Geom-GCN 的 embedding 空间维度为 2 ，并使用前面介绍的关系算子 $\tau$$\tau$ 。low-level 聚合函数 $p$$p$ 为均值聚合，high-level 聚合函数 $q$$q$ 为向量拼接。

     即 ${\overrightarrow{\mathbf{z}}}_v\in {\mathbb{R}}^2$$\mathbf {\vec z}_v\in \mathbb R^2$。

   • 所有模型的网络层数固定为 2，采用Adam 优化器。对于 Geom-GCN 和 GCN 我们采用 ReLU 作为激活函数，对于 GAT 我们采用 ELU 作为激活函数。

   • 我们使用验证集来搜索超参数，这些超参数包括：隐层维度、初始学习率、权重 decay、dropout。为确保公平，每个模型的超参数搜索空间都是相同的。最终得到的超参数配置为：

     • dropout rate = 0.5、初始化学习率 0.05、早停的 patience 为 100 个 epoch。

     • 对于 WebKB 数据集，weight decay 为 $5\times {10}^{-6}$$5\times 10^{-6}$ ；对于其它数据集，weight decay 为 $5\times {10}^{-5}$$5\times 10^{-5}$ 。

     • 对于 GCN 模型，隐层维度为：Cora 数据集 16、Citeseer 数据集 16、Pubmed 数据集 64、WebKB 数据集 32、Wikipedia 数据集 48、Actor 数据集 32 。

     • 对于 Geom-GCN 模型，隐层维度是 GCN 的 8 倍，因为 Geom-GCN 有 8 个虚拟节点。

       即 ${\overrightarrow{\mathbf{h}}}_v^{(l)}\in {\mathbb{R}}^2$$\mathbf {\vec h}_v^{(l)}\in \mathbb R^2$。

     • 对于 GAT 模型的每个 attention head，隐层维度为 Citation 网络为 8、WebKB 数据集为 32、Wikipedia 数据集为 48、Actor 数据集为 32 。

     • 对于 GAT 模型，第一层具有 8 个 head；Pubmed 数据集的第二层具有 8 个 head，其它数据集的第二层只有 1 个 head 。

   • 对于所有数据集，我们将每个类别的节点随机拆分为 60%, 20%, 20% 来分别作为训练集、验证集、测试集。

     我们随机拆分 10 次并报告模型在测试集上的平均性能。

4. 所有模型在所有数据集上的评估结果如下表所示，其中评估指标为平均分类准确率（以百分比表示）。最佳结果突出显式。

   结论：

   • Geom-GCN 可以实现 SOTA 性能。

   • 仅保留图中边和距离模式的 Isomap Embedding (Geom-GCN-I) 已经可以使得几何聚合方案受益。

   • 可以指定一种embedding 方法从而为特定应用构建合适的潜在空间，从而显著提升性能（如 Geom-GCN-P ）。

   

5. Geom-GCN 聚合了来自两个邻域的消息，这两个邻域分别在图空间和潜在空间中定义。这里我们通过构建仅有一个邻域的 Geom-GCN 变体来进行消融研究，从而评估每种邻域的贡献。

   • 对于仅具有图空间邻域的变体，我们用 g 后缀来区分（如 Geom-GCN-Ig）。

   • 对于仅具有潜在空间邻域的变体，我们用 s 后缀来区分(如 Geom-GCN-Is)。

   我们将 GCN 设为 baseline，从而评估这些变体相对 GCN 的性能提升。比较结果见下表所示，其中正向提升用向上箭头表示，负向衰减用向下箭头表示。评估指标为测试集的平均准确率。

   我们定义了指标 $\beta$$\beta$ 来衡量图的同质性 homophily：

   $$\beta =\frac{1}{|\mathcal{V}|}\sum _{v\in \mathcal{V}}\frac{\text{节}\text{点}v\text{邻}\text{域}\text{中}\text{和}v\text{标}\text{签}\text{相}\text{等}\text{的}\text{节}\text{点}\text{数}\text{量}}{\text{顶}\text{点}v\text{邻}\text{域}\text{的}\text{节}\text{点}\text{数}\text{量}}$$

   同质性以节点标签来衡量，其中相似的节点倾向于相互连接。较大的 $\beta$$\beta$ 值表示图的同质性很强。从下表可以看出，同配图（assortative graph）（如引文网络）具有比异配图（disassortative graph）（如 WebKB 网络）大得多的 $\beta$$\beta$ 值。

   结论：

   • 大多数情况下，图空间邻域和潜在空间邻域都有利于聚合。

   • 潜在空间邻域在异配图（更小的 $\beta$$\beta$ 值）上的提升要比同配图上的提升大得多。这意味着潜在空间邻域可以有效地捕获远程节点的相关信息。

     问题是：图空间邻域在异配图（更小的 $\beta$$\beta$ 值）上的提升，也是要比同配图上的提升大得多。因此图空间也可以有效捕获远程节点的相关信息？

     因此这里的结论不成立。

   • 令人惊讶的是，只有一个邻域的几种变体（下表）要比具有两个邻域的变体（上表）具有更好的性能。我们认为，原因是两个邻域的 Geom-GCN 相比单个邻域的 Geom-GCN 聚合了更多无关的消息，并且这些无关消息对于性能产生了不利的影响。

     我们认为注意力机制可以有效缓解这个问题，并留待以后工作进行研究。

   

6. Geom-GCN 的结构邻域非常灵活，可以组合任意的 embedding 空间。为了研究哪种 embedding 空间是理想的，我们通过采用由不同 embedding 空间构建的结构邻域来创建新的 Geom-GCN 变体。对于采用 Isomap 构建图空间邻域、采用 Poincare Embedding 构建潜在空间邻域的变体，我们用 Geom-GCN-IP 来表示。其它组合的命名规则依此类推。

   这里构建了两种潜在空间，从而得到 3 种类型的结构邻域（一个来自图控件，两个来自潜在空间）。

   下表给出了所有变体的性能，评估指标为测试集的平均准确率。

   结论：有一些组合的性能要优于标准的 Geom-GCN，有一些组合的性能更差。因此，如何设计自动选择合适的 embedding 空间的端到端框架是未来的重要方向。

   

7. 这里我们首先介绍Geom-GCN的理论时间复杂度，然后比较 GCN, GAT, Geom-GCN 的实际运行时间。

   Geom-GCN 更新一个节点的 representation 的时间复杂度为 $O(n\times d_h\times 2|\mathcal{R}|)$$O(n\times d_h\times 2|\mathcal R|)$ ，其中 $n$$n$ 为节点数量，$d_h$$d_h$ 为隐单元维度， $2|\mathcal{R}|$$2|\mathcal R|$ 为虚拟节点数量。相比之下 GCN 更新一个节点representation 的时间复杂度为 $O(n\times d_h)$$O(n\times d_h)$ 。

   我们给出所有数据集上 GCN, GAT, Geom-GCN 的实际运行时间（500 个 epoch）进行比较，结果如下图所示。 $y$$y$ 轴表示对数时间（秒）。

   结论：GCN 训练速度最快，GAT 和 Geom-GCN 处于同一水平。未来的一个重要方向是开发 Geom-GCN的加速技术，从而解决 Geom-GCN 的可扩展性。

   

8. 为研究 Geom-GCN 在节点feature representation 中学到的模式，我们可视化了 Cora 数据集在 Geom-GCN-P 模型最后一层得到的feature representation。我们通过 t-SNE 将该特征表示映射到二维空间中，如下图所示。节点的不同颜色代表不同的类别。

   可以看到：

   • 具有相同类别的节点表现出空间聚类（spatial clustering），这可以显示 Geom-GCN 的判别能力。

   • 图中所有节点均呈现放射状分布，这表明通过 Poincare Embedding 提出的 Geom-GCN 学到了图的层次结构。